package BinaryTree;
//给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
//
// 例如： 
//给定二叉树 [3,9,20,null,null,15,7], 
//
// 
//    3
//   / \
//  9  20
//    /  \
//   15   7
// 
//
// 返回其自底向上的层序遍历为： 
//
// 
//[
//  [15,7],
//  [9,20],
//  [3]
//]
// 
// Related Topics 树 广度优先搜索 二叉树 👍 505 👎 0


//leetcode submit region begin(Prohibit modification and deletion)


import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class levelOrderBottom {
    /**
     * 方法1 可以按照102的方法从上往下遍历结束，将结果逆转即可  accepted
     * 方法2 或者添加每层结果时，每次插到头部，res.add(0,list);
     * */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();  //利用队列层次
        List<List<Integer>> res = new ArrayList<>();  //结果集合
        //特殊情况处理
        if(root==null){
            return res;
        }
        //根节点入队列
        queue.offer(root);
        /**
         * 当队列不为空时，每次出队前的队列中节点数量即为同层节点的数量
         * 首先获取队列的大小len，出队len次,并添加其后继，即出队完这一层的节点
         * */
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int len = queue.size();
            while(len>0){
                TreeNode curr = queue.poll();
                list.add(curr.val);
                if(curr.left!=null){
                    queue.offer(curr.left);
                }
                if(curr.right!=null){
                    queue.offer(curr.right);
                }
                len--;
            }
//            res.add(list);
            //或者
            res.add(0,list); //每次插入集合头部
        }
//        Collections.reverse(res);
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
